
class Solution1 {
    public int numDecodings(String s) {
        if (s.length() == 0 || s.charAt(0) == '0') return 0;
        int n = s.length();
        if (n < 2) return 1;
        int[] dp = new int[n];

        if (s.charAt(0) != '0') dp[0] = 1;
        if (n == 1) return dp[0];

        if (s.charAt(1) != '0' && s.charAt(0) != '0') dp[1] += 1;
        int t = (s.charAt(0) - '0') * 10 + s.charAt(1) - '0';
        if (t >= 10 && t <= 26) dp[1] += 1;

        for (int i = 2; i < n; i++) {
            char c1 = s.charAt(i - 1), c2 = s.charAt(i);
            int x = (c1 - '0') * 10 + c2 - '0';
            if (c2 != '0') dp[i] += dp[i - 1];
            if (x >= 10 && x <= 26) dp[i] += dp[i - 2];
        }
        return dp[n - 1];
    }
}

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for(int i = 0; i<n;i++) {
            dp[0][i] = 1;
        }
        for(int i =0; i<m;i++) {
            dp[i][1] = 1;
        }
        for(int i = 1; i<m; i++) {
            for(int j = 1; j<n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}

public class Test {
}
